package com.cn.algorithm02.class22;

import java.util.HashMap;
import java.util.Map;
import java.util.Random;

/***
 * @author: hels
 * @description:
 *  arr数组是货币数组，一个值代表一张钱币，给定一个正数aim
 *  相同的纸币没有任何不同，返回组成aim的方法数
 *  例如：arr = {1,2,1,1,2,2,1} ,aim = 4
 *  方法：1111,112,22 因此返回3
 **/
public class C04_CoinsSameValueSamePaper {
    public static class Info {
        public int[] coins;
        public int[] zhangs;

        public Info(int[] c, int[] z) {
            coins = c;
            zhangs = z;
        }
    }

    public static Info getInfo(int[] arr) {
        HashMap<Integer, Integer> countsMap = new HashMap<>();
        for (int money : arr) {
            if (!countsMap.containsKey(money)) {
                countsMap.put(money, 1);
            } else {
                countsMap.put(money, countsMap.get(money) + 1);
            }
        }
        // arr数组转化为Info对象
        int[] coins = new int[countsMap.size()];
        int[] zhangs = new int[countsMap.size()];
        int index = 0;
        for (Map.Entry<Integer, Integer> entry : countsMap.entrySet()) {
            coins[index] = entry.getKey();
            zhangs[index++] = entry.getValue();
        }
        return new Info(coins, zhangs);
    }

    public static int coinsWay(int[] arr, int aim) {
        if (arr == null || aim < 0 || arr.length == 0) {
            return 0;
        }
        Info info = getInfo(arr);
        return process(info.coins, info.zhangs, 0, aim);
    }

    /**
     * 常规思路：暴力递归
     * @Param coins 钱币面值数组
     * @Param zhangs 货币张数数组
     * @Param index 下标标志
     * @Param rest 剩下多少钱
     */
    public static int process(int[] coins, int[] zhangs, int index, int rest) {
        if (index == coins.length) {
            return rest == 0 ? 1 : 0;
        }

        int way = 0;
        for (int zhang = 0; zhang * coins[index] <= rest && zhang <= zhangs[index]; zhang++) {
            way += process(coins, zhangs, index + 1, rest - zhang * coins[index]);
        }
        return way;
    }

    /**
     * 动态规划：常规递归思路转化
     */
    public static int dp1(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }

        Info info = getInfo(arr);
        int[] coins = info.coins;
        int[] zhangs = info.zhangs;
        int N = coins.length;
        int[][] dp = new int[N + 1][aim + 1];
        dp[N][0] = 1;

        for (int index = N - 1; index >= 0; index--) {
            for (int rest = 0; rest <= aim; rest++) {
                int ways = 0;
                for (int zhang = 0; zhang * coins[index] <= rest && zhang <= zhangs[index]; zhang++) {
                    ways += dp[index + 1][rest - zhang * coins[index]];
                }
                dp[index][rest] = ways;
            }
        }
        return dp[0][aim];
    }

    /**
     * 动态规划2，通过二维数组的形式进行统计计算
     * 有枚举行为可以通过观察临近位置进行推理，无枚举则推理至傻缓存则就是最优解
     */
    public static int dp2(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }

        Info info = getInfo(arr);
        int[] coins = info.coins;
        int[] zhangs = info.zhangs;
        int N = coins.length;
        int[][] dp = new int[N + 1][aim + 1];
        dp[N][0] = 1;
        for (int index = N - 1; index >= 0; index--) {
            for (int rest = 0; rest <= aim; rest++) {
                dp[index][rest] = dp[index + 1][rest];
                // 判断不越界，获得index、rest左边的值
                if (rest - coins[index] >= 0) {
                    dp[index][rest] += dp[index][rest - coins[index]];
                }
                if (rest - coins[index] * (zhangs[index] + 1) >= 0) {
                    dp[index][rest] -= dp[index + 1][rest - coins[index] * (zhangs[index] + 1)];
                }
            }
        }
        return dp[0][aim];
    }

    // 对数器：
    /** 创造数组, */
    public static int[] createArray(int maxValue, int maxLen) {
        int N = (int) (Math.random() * maxLen);
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            // 数组都是正数，有0会异常
            arr[i] = (int) (Math.random() * maxValue) + 1;
        }
        return arr;
    }

    public static void printArray(int[] arr, int aim) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + ", ");
        }
        System.out.println();
        System.out.println(aim);
    }

    public static void main(String[] args) {
        int maxValue = 20;
        int maxLen = 10;
        int times = 100;
        for (int i = 0; i < times; i++) {
            int[] arr = createArray(maxValue, maxLen);
            int aim = (int) (Math.random() * 200);
            int c1 = coinsWay(arr, aim);
            int c2 = dp1(arr, aim);
            int c3 = dp2(arr, aim);
            if (c1 != c2 || c1 != c3) {
                System.out.println("!!!wrong");
                printArray(arr, aim);
                System.out.println(c1);
                System.out.println(c2);
                System.out.println(c3);
                System.out.println("------------");
            }
        }
    }
}
